<?php
namespace QueueInfo;
include "ArrayInfo/ArrayBase.php";
include "Queue.php";

/**
 * 循环队列
 * Class LoopQueue
 */
class LoopQueue implements \QueueInfo\Queue
{
    private $data = [];
    private $front;
    private $tail;
    private $size;

    /**
     * 最大容量是10，循环队列浪费一个用来判断首尾
     * 这里使用：front == tail 来判定队列为空，所以 capacity + 1
     */
    private $max = 21;

    public function __construct(){
        $this->front = 0;
        $this->tail = 0;
        $this->size = 0;
    }

    /**
     * 获取循环队列容量
     * ($this->max) - 1 最大容量 - 1
     */
    public function getCapacity()
    {
        return $this->max - 1;
    }

    /**
     * @return int
     * 时间复杂度 O(1)
     */
    public function getSize()
    {
        // TODO: Implement getSize() method.
        return $this->size;
    }

    /**
     * @return bool
     * 时间复杂度 O(1)
     */
    public function isEmpty()
    {
        // TODO: Implement isEmpty() method.
        return $this->front == $this->tail;
    }

    /**
     * @param $e
     * 时间复杂度 O(1) 均摊
     * 入队
     */
    public function enqueue($e)
    {
        if(($this->tail + 1) % $this->max == $this->front){
            $this->max = $this->max * 2;
        }
        $this->data[$this->tail] = $e;
        $this->tail = ($this->tail + 1) % $this->max;
        $this->size++;
        
    }

    /**
     * @return mixed
     * 时间复杂度 O(1) 均摊
     * 出队
     */
    public function dequeue()
    {
        if($this->isEmpty()){
            echo "队列为空";
            return;
        }
        $ret = $this->data[$this->front];
        unset($this->data[$this->front]);
        // $this->data[$this->front] == null;
        $this->front = ($this->front + 1) % $this->max;
        $this->size--;
        return $ret;
    }

    /**
     * @return mixed
     * 时间复杂度 O(1)
     */
    public function getFront()
    {
        // TODO: Implement getFront() method.
        if($this->isEmpty()){
            echo "队列为空";
            return;
        }
        return $this->data[$this->front];
    }

    /**
     * Queue - 循环队列输出
     * @return string
     */
    public function toString()
    {
        printf('Queue：size=%d，capacity=%d',$this->getSize(),$this->getCapacity());
        echo "\n";
        $str = 'front [';
        for ($i = $this->front;$i != $this->tail; $i = ($i+1) % $this->max) {
            $str .= $this->data[$i];
            if(($i + 1) % $this->max != $this->tail){
                $str .= ", ";
            }
        }
        $str .= '] tail';
        return $str;
    }
}
